package com.zjsru.oneday202208;

/**
 * @Author: likew
 * @Date: 2022/8/28 阶乘函数后 K 个零 f(x)是x!末尾是 0 的数量。回想一下x! = 1 * 2 * 3 * ... * x，且 0! = 1。
 * <p>
 * 例如，f(3) = 0，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2，因为 11!= 39916800 末端有 2 个 0 。 给定k，找出返回能满足 f(x) = k的非负整数 x的数量。
 * <p>
 * 输入：k = 0 输出：5 解释：0!, 1!, 2!, 3!, 和 4! 均符合 k = 0 的条件。
 */
public class PreimageSizeFZF {
    
    public int preimageSizeFZF(int k) {
        if (k <= 1) {
            return 5;
        }
        return f(k) - f(k - 1);
    }
    
    private int f(int k) {
        long l = 0, r = (long) 1e10;
        while (r > l) {
            long mid = l + r + 1 >> 1;
            if (getCnt(mid) <= k) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return (int) r;
    }
    
    private long getCnt(long x) {
        long ans = 0;
        while (x != 0) {
            ans += x / 5;
            x /= 5;
        }
        return ans;
    }
    
    public static void main(String[] args) {
        PreimageSizeFZF preimageSizeFZF = new PreimageSizeFZF();
        int k = 2;
        System.out.println(preimageSizeFZF.preimageSizeFZF(k));
    }
}
